import java.util.Deque;
import java.util.LinkedList;

public class Solution227 {
    public int calculate(String s) {
        Deque<Integer> nums = new LinkedList<>();
        Deque<Character> operators = new LinkedList<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (Character.isDigit(c)) {
                int num = 0;
                while (i < s.length() && Character.isDigit(s.charAt(i))) {
                    num = num * 10 + s.charAt(i) - '0';
                    i++;
                }
                i--;
                nums.push(num);
            } else if (c == '+' || c == '-') {
                while (!operators.isEmpty()) {
                    nums.push(calculate(nums.poll(), nums.poll(), operators.poll()));
                }
                operators.push(c);
            } else if (c == '*' || c == '/') {
                while (!operators.isEmpty()) {
                    Character o = operators.poll();
                    if (o == '*' || o == '/') {
                        nums.push(calculate(nums.poll(), nums.poll(), o));
                    } else {
                        operators.push(o);
                        break;
                    }
                }
                operators.push(c);
            }
        }
        while (!operators.isEmpty()) {
            nums.push(calculate(nums.poll(), nums.poll(), operators.poll()));
        }
        return nums.peek();
    }

    int calculate(Integer b, Integer a, Character o) {
        if (o == '+') {
            return a + b;
        }
        if (o == '-') {
            return a - b;
        }
        if (o == '*') {
            return a * b;
        }
        if (o == '/') {
            return a / b;
        }
        return -1;
    }
}
